By leveraging the topological order of a Directed Acyclic Graph (DAG), we can find the shortest path in a highly efficient, linear time complexity.

  • Requires two main steps: Topological Sort followed by ordered relaxation.
  • Step 1: Compute the topological sort of the DAG, resulting in a list of nodes.
  • Step 2: Initialize distances: source node to \(0\), all other nodes to \(\infty\).
  • Step 3: Iterate through the topologically sorted list, relaxing all outgoing edges for the current node.
  • The total time complexity is \(O(V + E)\), which is linear and optimal for graph traversal.
  • Why is this faster than Dijkstra? Dijkstra's algorithm uses a priority queue to greedily select the next closest node, adding a logarithmic factor (\(O(\log V)\)). In a DAG, the topological sort provides a fixed, optimal order for relaxation, eliminating the need for a priority queue. We simply process nodes one by one.
  • Why does it handle negative weights? The topological order guarantees that by the time we process a node \(u\), the shortest paths to all nodes that can reach \(u\) have already been finalized. This non-greedy approach allows for negative weights, as we won't prematurely "lock in" a path before considering all possibilities, which is a potential failure point for Dijkstra's algorithm.
Python: DAG Shortest Path Algorithm
1def dag_shortest_path(graph, start):
2    sorted_list = topological_sort(graph)
3
4    distances = {node: float('inf') for node in graph}
5    distances[start] = 0
6
7    # Step 3: Loop in topological order
8    for node in sorted_list:
9        if distances[node] == float('inf'):
10            continue # Can't reach this node
11
12        # Relax all neighbors
13        for neighbor, weight in graph[node].items():
14            new_distance = distances[node] + weight
15            if new_distance < distances[neighbor]:
16                distances[neighbor] = new_distance
17
18    return distances